/**
 * @version: V1.0
 * @Title: Trie.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-13 22:19
 * @Copyright: 2022-01-13
 */

package com.peng.trie;

/**
 * @author wangshipeng
 * @ClassName: Trie
 * @Description: 前缀树实现
 * @date 2022-01-13 22:19
 */
public class MyTrie {


    private Node root;

    public MyTrie() {
        root = new Node();
    }

    public static void main(String[] args) {
        MyTrie trie = new MyTrie();
        trie.insert("abc");
        trie.insert("abc");
        trie.insert("abc");
        trie.insert("abcef");
        trie.insert("abcefgh");
        System.out.println(trie.search("abc"));
        System.out.println(trie.prefix("abc"));
        trie.delete("abc");
        System.out.println(trie.search("abcef"));
        System.out.println(trie.prefix("abc"));

    }

    public void insert(String word) {
        if (word == null) {
            return;
        }
        Node curNode = root;
        curNode.pass++;
        int path;
        for (char letter : word.toCharArray()) {
            path = letter - 'a';
            if (curNode.nexts[path] == null) {
                curNode.nexts[path] = new Node();
            }
            curNode = curNode.nexts[path];
            curNode.pass++;
        }
        curNode.end++;

    }

    /**
     * 检索单词在Trie中出现的次数
     *
     * @param word
     * @return
     */
    public int search(String word) {
        if (word == null) {
            return 0;
        }
        Node curNode = root;
        int path;
        for (char letter : word.toCharArray()) {
            path = letter - 'a';
            if (curNode.nexts[path] == null) {
                return 0;
            }
            curNode = curNode.nexts[path];
        }
        return curNode.end;

    }

    /**
     * 检索单词在Trie中出现前缀的次数
     *
     * @param word
     * @return
     */
    public int prefix(String word) {
        if (word == null) {
            return 0;
        }
        Node curNode = root;
        int path;
        for (char letter : word.toCharArray()) {
            path = letter - 'a';
            if (curNode.nexts[path] == null) {
                return 0;
            }
            curNode = curNode.nexts[path];
        }
        return curNode.pass;

    }

    public void delete(String word) {
        if (search(word) > 0) {
            Node curNode = root;
            curNode.pass--;
            int path;
            for (char letter : word.toCharArray()) {
                path = letter - 'a';

                //如果在当前节点，减少pass后已经为0，说明此路径只此一个单词
                //所以作为优化，不需要再向后，直接切断与后续路径的连接，等待GC回收即可
                if (--curNode.nexts[path].pass == 0) {
                    curNode.nexts[path] = null;
                    return;
                }
                curNode = curNode.nexts[path];
            }
            curNode.end--;
        }
    }

    private static class Node {
        //有多少个字符经过了此节点
        private int pass;
        //有多少字符以此节点结尾
        private int end;

        //后续的节点
        private Node[] nexts;

        public Node() {
            pass = 0;
            end = 0;
            nexts = new Node[26];
        }


    }


}
